package com.ryujung.dp.leetCode_10;

/*
 * @lc app=leetcode.cn id=10 lang=java
 *
 * [10] 正则表达式匹配
 */

// @lc code=start
class Solution {

    /**
     * 有限状态机方法 FIXME 暂时搞不定
     */
    public static boolean isMatch3(String s, String p) {

        return false;
    }

    public boolean isMatch4(String s, String p) {
        char[] sc = s.toCharArray();
        char[] pc = (p + ")").toCharArray();

        int m = pc.length + 1;
        boolean[][] graph = new boolean[m][m];
        for (int i = 0; i < m - 1; i++) {
            if (pc[i] == '*') {
                // 匹配到星号字符时，初始化
                graph[i - 1][i] = true;
                graph[i][i - 1] = true;
                graph[i][i + 1] = true;
            } else if (pc[i] == ')') {
                graph[i][i + 1] = true;
            }
        }

        boolean[] mark = dfs(graph, 0);
        for (int i = 0; i < sc.length; i++) {
            boolean[] match = new boolean[m];
            for (int j = 0; j < m; j++) {
                if (mark[j]) {
                    if (j == m - 1) {
                        continue;
                    }

                    if (pc[j] == sc[i] || pc[j] == '.') {
                        match[j + 1] = true;
                    }
                }
            }

            mark = dfs(graph, match);
        }

        return mark[m - 1];
    }

    private boolean[] dfs(boolean[][] graph, int s) {
        boolean[] re = new boolean[graph.length];
        doDfs(graph, re, s);

        return re;
    }

    private boolean[] dfs(boolean[][] graph, boolean[] mark) {
        boolean[] re = new boolean[graph.length];
        for (int i = 0; i < mark.length; i++) {
            if (mark[i]) {
                doDfs(graph, re, i);
            }
        }

        return re;
    }

    private void doDfs(boolean[][] graph, boolean[] mark, int v) {
        mark[v] = true;
        for (int i = 0; i < graph.length; i++) {
            if (!mark[i] && graph[v][i]) {
                doDfs(graph, mark, i);
            }
        }
    }

    /**
     * 尝试官方思路
     */
    public static boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        // dp代表s的前i个字符与p的前j个字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char c = p.charAt(j - 1);
                if (c == '*') {
                    if (match(s, p, i, j - 1)) {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                } else {
                    if (match(s, p, i, j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 检查s的第i个字符和p的第j个字符是否匹配
     */
    public static boolean match(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }

        if (p.charAt(j - 1) == '.') {
            return true;
        } else {
            return p.charAt(j - 1) == s.charAt(i - 1);
        }
    }

    public static void main(String[] args) {
        String s = "aa";
        String p = "a*";
        System.out.println("匹配结果为：" + isMatch(s, p));
    }

}
// @lc code=end
